package neo.aoi.octree;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;

import neo.aoi.Triangle;
import neo.aoi.Vec3Set;
import neo.aoi.Voxel;
import Jama.util.Maths;
import artofillusion.Scene;
import artofillusion.math.BoundingBox;
import artofillusion.math.CoordinateSystem;
import artofillusion.math.Vec3;
import artofillusion.object.CSGObject;
import artofillusion.object.Cube;
import artofillusion.object.Object3D;
import artofillusion.object.ObjectInfo;
import artofillusion.object.TriangleMesh;
import artofillusion.object.TriangleMesh.Face;

/**
 * This class provides a set of functions for converting 3D shapes from a
 * Triangle mesh representation to discrete element representation using volume
 * elements or Voxels.
 * 
 * @author Mauro Santos
 * 
 */
public class OctreeBuilder {

	private TriangleMesh.Face[] scenarioTriangleList;

	public static Set<OctreeVoxel> octreeVoxels = new HashSet<OctreeVoxel>();

	public static OctreeNode unOctreeNode;

	/**
	 * Takes a the vertices of a triangle, and divides places it in a voxel grid
	 * of the specified resolution. The coordinates of the voxels which
	 * intersect with the given triangle are returned. This method creates a
	 * voxel at every point where the faces of the generated TriangleMesh
	 * intersect the voxel grid.
	 * 
	 * @param va
	 *            Vertex of the triangle
	 * @param vb
	 *            Vertex of the triangle
	 * @param vc
	 *            Vertex of the triangle
	 * @param res
	 *            Resolution of the voxel grid
	 * @param objectGridCoord
	 *            Object grid coordinates
	 * @return A Set of Vec3 objects which represents the coordinates of the
	 *         produced Voxels.
	 */
	public static Set<Vec3> getVoxels(Vec3 va, Vec3 vb, Vec3 vc, double res,
			Vec3 objectGridCoord) {
		Set<Vec3> voxels = new Vec3Set(res);

		Triangle t = new Triangle(va, vb, vc);
		BoundingBox bounds = t.getBoundingBox();

		// Find Max and mins
		double maxX = bounds.maxx;
		double minX = bounds.minx;
		double maxY = bounds.maxy;
		double minY = bounds.miny;
		double maxZ = bounds.maxz;
		double minZ = bounds.minz;

		// Find ranges to be used - 1 voxel slack
		double lowX = minX - (minX % res) - res;
		double highX = maxX + (res - (maxX % res)) % res + res;
		double lowY = minY - (minY % res) - res;
		double highY = maxY + (res - (maxY % res)) % res + res;
		double lowZ = minZ - (minZ % res) - res;
		double highZ = maxZ + (res - (maxZ % res)) % res + res;

		// Iterate through the grid
		for (double x = lowX; x < highX; x += res) {
			double cx = x;// Voxel center X
			for (double y = lowY; y < highY; y += res) {
				double cy = y;// Voxel center Y
				for (double z = lowZ; z < highZ; z += res) {
					double cz = z;// Voxel center Z

					Voxel v = new Voxel(new Vec3(cx, cy, cz), res);
					if (v.intersects(t)) {
						voxels.add(new Vec3(x + objectGridCoord.x, y
								+ objectGridCoord.y, z + objectGridCoord.z));
					}
				}
			}
		}
		return voxels;
	}

	/**
	 * Converts an Object3D object to its equivalente voxel representation.
	 * Before being converted to voxels, the Object3D is converted to
	 * TriangleMesh using the given tolerance. Voxels are sampled using the
	 * given resolution. This method creates a voxel at every point where the
	 * faces of the generated TriangleMesh intersect the voxel grid.
	 * 
	 * @param obj3D
	 *            The Object3D to be converted to voxels.
	 * @param tol
	 *            The specified tolerance as specified by
	 *            artofillusion.object.Object3D.convertToTriangleMesh(double)
	 * @param res
	 *            Resolution of the voxel grid
	 * @see artofillusion.object.Object3D#convertToTriangleMesh(double)
	 * @return A Set of Vec3 objects which represents the coordinates of the
	 *         produced Voxels.
	 */
	public static Set<Vec3> getVoxels(Object3D obj3D, double tol, double res,
			CoordinateSystem coords) {
		TriangleMesh tmesh = obj3D.convertToTriangleMesh(tol);
		TriangleMesh.Face[] faces = tmesh.getFaces();
		// Mauro:this is just to get the size of the vertex vector!
		Vec3[] vertex = tmesh.getVertexPositions();

		double coordX = coords.getOrigin().x;
		double coordY = coords.getOrigin().y;
		double coordZ = coords.getOrigin().z;

		// Find object coordinates in the grid
		double lowXCoord = coordX - (coordX % res);
		double lowYCoord = coordY - (coordY % res);
		double lowZCoord = coordZ - (coordZ % res);
		double highXCoord = coordX + (res - (coordX % res)) % res;
		double highYCoord = coordY + (res - (coordY % res)) % res;
		double highZCoord = coordZ + (res - (coordZ % res)) % res;

		double xc = lowXCoord;
		double yc = lowYCoord;
		double zc = lowZCoord;
		if (Math.abs((coordX - lowXCoord)) > Math.abs((highXCoord - coordX))) {
			xc = highXCoord;
		} else {
			xc = lowXCoord;
		}
		if (Math.abs((coordY - lowYCoord)) > Math.abs((highYCoord - coordY))) {
			yc = highYCoord;
		} else {
			yc = lowYCoord;
		}
		if (Math.abs((coordZ - lowZCoord)) > Math.abs((highZCoord - coordZ))) {
			zc = highZCoord;
		} else {
			zc = lowZCoord;
		}

		Vec3 objectGridCoord = new Vec3(xc, yc, zc);

		Set<Vec3> voxels = new Vec3Set(res);
		// Convert triangle mesh to voxels
		for (int j = 0; j < faces.length; j++) {
			Set<Vec3> vox_face = getVoxels(vertex[faces[j].v1],
					vertex[faces[j].v2], vertex[faces[j].v3], res,
					objectGridCoord);
			voxels.addAll(vox_face);
		} // For_j

		return voxels;
	}

	/**
	 * Converts the given 3D object to its voxel representation filling the
	 * interior space of the object with voxels too. Before being converted to
	 * voxels, the Object3D is converted to TriangleMesh using the given
	 * tolerance. Voxels are sampled using the given resolution. This method
	 * creates a voxel at each point where object intersects the voxel grid
	 * using constructive solid geometry.
	 * 
	 * @param obj
	 *            the 3D object to be exported.
	 * @param tol
	 *            The specified tolerance as specified by
	 *            artofillusion.object.Object3D.convertToTriangleMesh(double)
	 *            Resolution of the voxel grid
	 * @see artofillusion.object.Object3D#convertToTriangleMesh(double)
	 * @return A Set of Vec3 objects which represents the coordinates of the
	 *         produced Voxels.
	 */
	public static Set<Vec3> getVoxelsWithFilling(Object3D obj, double tol,
			double res, CoordinateSystem coords) {
		Set<Vec3> voxels = new Vec3Set(res);
		BoundingBox bounds = obj.getBounds();
		double deltaX = bounds.minx + (bounds.maxx - bounds.minx) / 2;
		double deltaY = bounds.miny + (bounds.maxy - bounds.miny) / 2;
		double deltaZ = bounds.minz + (bounds.maxz - bounds.minz) / 2;

		ObjectInfo objinfo = new ObjectInfo(obj, new CoordinateSystem(new Vec3(
				-deltaX, -deltaY, -deltaZ), 0, 0, 0), "Objeto");
		Object3D ip = new Cube(1.1 * (bounds.maxx - bounds.minx),
				1.1 * (bounds.maxy - bounds.miny), res); // Intersection
		// Plane

		for (double z = bounds.minz; z <= bounds.maxz; z += res) {
			ObjectInfo ip_info = new ObjectInfo(ip, new CoordinateSystem(
					new Vec3(0, 0, z), 0, 0, 0), "cubo");

			CSGObject intersection = new CSGObject(objinfo, ip_info,
					CSGObject.INTERSECTION);
			voxels.addAll(OctreeBuilder.getVoxels(intersection, tol, res,
					coords));
		}

		return voxels;
	}

	public static int getScenarioNumberOfFaces(
			List<TriangleMesh.Face[]> scenarioFaces) {

		int sum = 0;
		for (Face[] faces : scenarioFaces) {
			sum = sum + faces.length;
		}
		return sum;
	}

	public static Face[] getAllScenarioFaces(
			List<TriangleMesh.Face[]> scenarioFaces, int nrOfFaces) {
		TriangleMesh.Face[] scenefaces = new TriangleMesh.Face[nrOfFaces];
		int k = 0;
		for (Face[] faces : scenarioFaces) {
			for (Face face : faces) {
				scenefaces[k] = face;
				k = k + 1;
			}
		}
		return scenefaces;
	}

	public static BoundingBox getCubeScenarioBoundingBox(
			List<BoundingBox> boundingBoxList) {

		BoundingBox sceneBoundingBox = new BoundingBox(0, 0, 0, 0, 0, 0);
		if (!boundingBoxList.isEmpty()) {
			BoundingBox bd0 = boundingBoxList.get(0);
			double maxX = bd0.maxx;
			double maxY = bd0.maxy;
			double maxZ = bd0.maxz;
			double minX = bd0.minx;
			double minY = bd0.miny;
			double minZ = bd0.minz;
			for (BoundingBox boundingBox : boundingBoxList) {

				if (boundingBox.maxx > maxX) {
					maxX = boundingBox.maxx;
				}
				if (boundingBox.maxy > maxY) {
					maxY = boundingBox.maxy;
				}
				if (boundingBox.maxz > maxZ) {
					maxZ = boundingBox.maxz;
				}

				if (boundingBox.minx < minX) {
					minX = boundingBox.maxx;
				}
				if (boundingBox.miny < minY) {
					minY = boundingBox.maxy;
				}
				if (boundingBox.minz < minZ) {
					minZ = boundingBox.maxz;
				}

			}

			double[] sizes = { Math.abs(maxX - minX), Math.abs(maxY - minY),
					Math.abs(maxZ - minY) };
			System.out.println("sizes:scenarioBoundingBox:res:1:" + sizes[0]
					+ "2:" + sizes[1] + "3:" + sizes[2]);
			double res = getMaxValue(sizes);
			System.out.println("inside:scenarioBoundingBox:res:" + res);
			// double highX = maxX + (res - (maxX % res)) % res;
			// double highY = maxY + (res - (maxY % res)) % res;
			// double highZ = maxZ + (res - (maxZ % res)) % res;

			sceneBoundingBox = new BoundingBox(minX, minX + res, minY, minY
					+ res, minZ, minZ + res);
		}

		return sceneBoundingBox;
	}

	public static double getMaxValue(double[] numbers) {
		double maxValue = numbers[0];
		for (int i = 0; i < numbers.length; i++) {
			if (numbers[i] > maxValue) {
				maxValue = numbers[i];
			}
		}
		return maxValue;
	}

	/**
	 * Converts all Object3D objects in a scenario to it's faces representation
	 * 
	 * @param scene
	 *            The Scene with objects to be converted to Faces.
	 * @param tol
	 *            The specified tolerance as specified by
	 *            artofillusion.object.Object3D.convertToTriangleMesh(double)
	 * @param res
	 *            Resolution of the voxel grid
	 * @see artofillusion.object.Object3D#convertToTriangleMesh(double)
	 * @return A Set of Vec3 objects which represents the coordinates of the
	 *         produced Voxels.
	 */
	public static OctreeNode buildOctree(Scene scene, double tol,
			double maxRes) {

		List<TriangleMesh> meshList = new ArrayList<TriangleMesh>();
		List<BoundingBox> boundingBoxList = new ArrayList<BoundingBox>();
		List<TriangleMesh.Face[]> facesList = new ArrayList<TriangleMesh.Face[]>();
		Set<Triangle> sceneTriangles = new HashSet<Triangle>();
		List<BoundingBox> objBoundingBoxList = new ArrayList<BoundingBox>();
		List<BoundingBox> sceneObjBoundingBoxList = new ArrayList<BoundingBox>();
		BoundingBox[] objBounds = new BoundingBox[scene.getAllObjects().size()];
		int i = 0;
		for (ObjectInfo objInfo : scene.getAllObjects()) {
			Object3D obj3D = objInfo.object;
			Vec3 objPos = objInfo.getCoords().getOrigin();
			if (obj3D.canConvertToTriangleMesh() != Object3D.CANT_CONVERT) {
				TriangleMesh tmesh = obj3D.convertToTriangleMesh(tol);
				meshList.add(tmesh);
				facesList.add(tmesh.getFaces());

				Vec3[] vertex = tmesh.getVertexPositions();
				TriangleMesh.Face[] faces = tmesh.getFaces();

				for (int j = 0; j < tmesh.getFaces().length; j++) {
					sceneTriangles.add(new Triangle(vertex[faces[j].v1]
							.plus(objPos), vertex[faces[j].v2].plus(objPos),
							vertex[faces[j].v3].plus(objPos)));
				}
				BoundingBox tmeshBound = tmesh.getBounds();
				boundingBoxList.add(tmesh.getBounds());
				sceneObjBoundingBoxList.add(new BoundingBox(tmeshBound.minx
						+ objPos.x, tmeshBound.maxx + objPos.x, tmeshBound.miny
						+ objPos.y, tmeshBound.maxy + objPos.y, tmeshBound.minz
						+ objPos.z, tmeshBound.maxz + objPos.z));
				objBoundingBoxList.add(obj3D.getBounds());
				objBounds[i] = obj3D.getBounds();
				i = i + 1;
			}
		}

		// get faces count
		// int countScenarioFaces = getScenarioNumberOfFaces(facesList);
		// get all scenario faces
		// TriangleMesh.Face[] scenefaces = getAllScenarioFaces(facesList,
		// countScenarioFaces);

		// Scenario Bounding Box
		BoundingBox scenarioBoundingBox = getCubeScenarioBoundingBox(sceneObjBoundingBoxList);
		
		BoundingBox bb= scenarioBoundingBox;
		double x=Math.abs(bb.maxx-bb.minx);
		double y=Math.abs(bb.maxy-bb.miny);
		double z=Math.abs(bb.maxz-bb.minz);
		
		double[] arrayD= {x,y,z};
		Arrays.sort(arrayD);
		double side=arrayD[arrayD.length-1];
		Vec3 center= scenarioBoundingBox.getCenter();
		BoundingBox cubicBounding=new BoundingBox(center.x+side/2,
				center.x-side/2,
				center.y+side/2, 
				center.y-side/2, 
				center.z+side/2,
				center.z-side/2);
				
//		double maxX=scenarioBoundingBox.maxx;
//		double maxY=scenarioBoundingBox.maxy;
//		double maxZ=scenarioBoundingBox.maxz;
//		double minZ=scenarioBoundingBox.minz;
//		double minX=scenarioBoundingBox.minx;
//		double minY=scenarioBoundingBox.miny;
		// Find ranges to be used - 1 voxel slack
//		double lowX = minX - (minX % maxRes) - maxRes;
//		double highX = maxX + (maxRes - (maxX % maxRes)) % maxRes + maxRes;
//		double lowY = minY - (minY % maxRes) - maxRes;
//		double highY = maxY + (maxRes - (maxY % maxRes)) % maxRes + maxRes;
//		double lowZ = minZ - (minZ % maxRes) - maxRes;
//		double highZ = maxZ + (maxRes - (maxZ % maxRes)) % maxRes + maxRes;
		
		double cubicSide=Math.abs(cubicBounding.maxx-cubicBounding.minx);
		
		double s=1;
		double goodSize=0;
		while(true){
			goodSize=maxRes*Math.pow(2, s);
			if(goodSize>=cubicSide){
				break;
			}
			s=s+1;
		}
		
		cubicBounding.outset((goodSize-cubicSide)/2);
		
		double lowX = cubicBounding.minx;
		double highX = cubicBounding.maxx;
		double lowY = cubicBounding.miny;
		double highY =cubicBounding.maxy;
		double lowZ = cubicBounding.minz;
		double highZ = cubicBounding.maxz;
		
		// System.out.println("scenarioBoundingBox:"
		// + scenarioBoundingBox.toString());

		Triangle[] triangleList = new Triangle[sceneTriangles.size()];

		triangleList = (Triangle[]) sceneTriangles.toArray(new Triangle[scene
				.getAllObjects().size()]);
		// System.out.println("objectList:" + triangleList.toString());

		OctreeNode rootNode = new OctreeNode(lowX,
				highX,lowY,highY,lowZ,
				highZ, triangleList, null, maxRes);
		// System.out.println("rootNode:" + rootNode.toString());
		return rootNode;

	}

	public static void getOctreeVoxels(OctreeNode octreeNode) {

		if (octreeNode.findChildNodes().length == 0) {

			octreeVoxels.add(new OctreeVoxel(new Vec3(octreeNode.minx,
					octreeNode.miny, octreeNode.minz), octreeNode.res,
					octreeNode.depth, octreeNode.index));
			return;
		}

		for (OctreeNode childOctreeNode : octreeNode.findChildNodes()) {
			getOctreeVoxels(childOctreeNode);
		}
	}

	public static List<Integer> getNeighbours(OctreeVoxel ov,
			Set<OctreeVoxel> octreeVoxels, double min) {

		double res = ov.getRes();
		double x1 = ov.getVoxel().x - min;
		double y1 = ov.getVoxel().y - min;
		double z1 = ov.getVoxel().z - min;
		double x2 = ov.getVoxel().x + res + min;
		double y2 = ov.getVoxel().y + res + min;
		double z2 = ov.getVoxel().z + res + min;
		BoundingBox b1 = new BoundingBox(x1, x2, y1, y2, z1, z2);

		List<Integer> i = new ArrayList<Integer>();

		for (OctreeVoxel ov3 : octreeVoxels) {
			double res2 = ov3.getRes();
			double xx1 = ov3.getVoxel().x;
			double yy1 = ov3.getVoxel().y;
			double zz1 = ov3.getVoxel().z;
			double xx2 = ov3.getVoxel().x + res2;
			double yy2 = ov3.getVoxel().y + res2;
			double zz2 = ov3.getVoxel().z + res2;
			BoundingBox b2 = new BoundingBox(xx1, xx2, yy1, yy2, zz1, zz2);

			if (b1.intersects(b2)) {
				i.add(ov3.getIndex());
			}

		}
		return i;
	}

	public static MaxIndexAndMinRes getMaxIndexAndMinRes() {
		double min = 0;
		int aux = 0;
		int maxIndex = 0;
		for (OctreeVoxel ov2 : octreeVoxels) {
			if (aux == 0) {
				maxIndex = ov2.getIndex();
				min = ov2.getRes();
			} else {
				if (min > ov2.getRes()) {
					min = ov2.getRes();
				}

				if (maxIndex < ov2.getIndex()) {
					maxIndex = ov2.getIndex();
				}
			}

			aux = aux + 1;

		}

		return new MaxIndexAndMinRes(maxIndex, min);

	}

	public static void getBalancedOctreeVoxels(int maxIndex, double minRes) {

		Map<Integer, OctreeVoxel> oVmap = new HashMap<Integer, OctreeVoxel>();

		for (OctreeVoxel ov2 : octreeVoxels) {
			oVmap.put(ov2.getIndex(), ov2);
		}

		Map<Integer, List<Integer>> mapN = new HashMap<Integer, List<Integer>>();
		for (OctreeVoxel ov2 : octreeVoxels) {
			mapN.put(ov2.getIndex(), getNeighbours(ov2, octreeVoxels, minRes));
		}
		int indexToDivide = -1;

		for (OctreeVoxel ov2 : octreeVoxels) {
			for (Integer i : mapN.get(ov2.getIndex())) {
				int d1 = ov2.getDepth();
				int d2 = oVmap.get(i).getDepth();
				if (Math.abs(d1 - d2) >= 2) {
					if (d1 > d2)
						indexToDivide = ov2.getIndex();
					break;
				} else {
					indexToDivide = oVmap.get(i).getIndex();
					break;
				}
			}
		}
		if (indexToDivide != -1) {
			divideOctreeNode(unOctreeNode, indexToDivide, maxIndex);
			octreeVoxels.clear();
			getOctreeVoxels(unOctreeNode);
			getBalancedOctreeVoxels(maxIndex + 9, minRes);

		} else {
			return;
		}
	}

	public static void divideOctreeNode(OctreeNode octreeNode,
			int indexToDivide, int maxIndex) {

		if (octreeNode.index == indexToDivide) {
			octreeNode.divide(maxIndex);
			return;
		}

		for (OctreeNode childOctreeNode : octreeNode.findChildNodes()) {
			divideOctreeNode(childOctreeNode, indexToDivide, maxIndex);
		}
	}

	public TriangleMesh.Face[] getScenarioTriangleList() {
		return scenarioTriangleList;
	}

	public void setScenarioTriangleList(TriangleMesh.Face[] scenarioTriangleList) {
		this.scenarioTriangleList = scenarioTriangleList;
	}

	public Set<OctreeVoxel> getVoxels() {
		return octreeVoxels;
	}

	public static void markOctreeVoxels(Set<BoundingBox> bbList, double res,
			int objectId) {

		for (BoundingBox bb : bbList) {

			for (OctreeVoxel ov3 : octreeVoxels) {
				double res2 = ov3.getRes();
				double xx1 = ov3.getVoxel().x;
				double yy1 = ov3.getVoxel().y;
				double zz1 = ov3.getVoxel().z;
				double xx2 = ov3.getVoxel().x + res2;
				double yy2 = ov3.getVoxel().y + res2;
				double zz2 = ov3.getVoxel().z + res2;
				BoundingBox b2 = new BoundingBox(xx1, xx2, yy1, yy2, zz1, zz2);

				if (bb.intersects(b2)) {

					if (ov3.getObjectId() == 0)
						ov3.setObjectId(objectId);
					ov3.setConductivity(objectId);
				}

			}

		}
	}

}
